package offer.secnod;

public class Offer12 {
    boolean res=false;

    public  boolean  judge(char[][] board,String word){
        int m = board.length;
        int n = board[0].length;
        char[] chars = word.toCharArray();
        for (int i = 0; i <=m ; i++) {
            for (int j = 0; j <=n ; j++) {
            res= dfs(board,chars,i,j,0);
                if (res){
                    return res;
                }
            }
        }
        return  res;
    }

    public boolean  dfs(char[][]  board,char[] words,int x,int y,int k){
//        if (x<0||y<0||x>= board.length||y>=board[0].length||k>=words.length||board[x][y]==' '||words[k]!= board[x][y]){
//            return  false;
//        }
        if (x<0||y<0||x>= board.length||y>=board[0].length||words[k]!= board[x][y]){
            return  false;
        }

        //TODO:2023/8/18 第一步少了这一步  确实是k=words.length-1  就可以返回 因为上面的if中已经判断了 words[k]== board[x][y]
        // 也就是words的最后一个字符已经被验证过了
        if(k==words.length-1)
            return true;

        board[x][y]=' ';
        res=dfs(board, words, x+1, y, k+1)||
                dfs(board, words, x-1, y, k+1)||
                dfs(board, words, x, y-1, k+1)||
                dfs(board, words, x, y+1, k+1);
        board[x][y]=words[k];

        return  res;
    }

    public static void main(String[] args) {

        Offer12 offer12 = new Offer12();
        char[][]  ju={{'a'}};
        System.out.println(offer12.judge(ju, "a"));
    }

}
